import com.clq.Application;
import com.clq.job.DataJob;
import org.apache.catalina.LifecycleState;
import org.nutz.json.Json;
import sun.reflect.Reflection;

import java.lang.annotation.Annotation;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by clq on 2018/12/27.
 */
public class Sort {
    static int aux[];
    public static void main(String[] args) throws NoSuchMethodException, ClassNotFoundException, IllegalAccessException, InstantiationException, InvocationTargetException {
        //bubuleSort();
        //insertSort();
        //selectSort();
        //shellSort();
        /*int a[] = {12,2,0,4,3,2,6788823,2,0,4,3,2};
        aux = new int[a.length];
        sort(a, 0, a.length-1);
        for(int a1 : a) {
            System.out.println(a1);
        }*/
        hash();
       /* String str = "sdgsdfgsdgf";
        String substring = str.substring(1, 2);
        String[] ds = str.split("d");
        System.out.println(str+ "," + substring+","+ Json.toJson(ds));*/
        //Annotation[] annotations = Application.class.getAnnotations();
        //Method main = Application.class.getMethod("main", String[].class);
       // main.invoke(main,)
        //System.out.println(Json.toJson(main));

        //Class<?> aClass = Class.forName("com.clq.Application");
        //Application application = (Application)aClass.newInstance();
        //application.main(new String[]{});

        //Method main1 = aClass.getMethod("main", String[].class);
        //main1.invoke(main1, new String[]{});
    }

    public static void bubuleSort() {
        int arr[] = {12,234,1,123,888,45,12,234,1,123,45,23,2,234,1,123,45,23,2,0,4,3,2,6788823,2,0,4,3,2,67888};
        for(int i=0; i<arr.length;i++) {
            for(int j=i; j<arr.length; j++) {
                if(arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int i: arr
             ) {
            System.out.println(i);
        }
    }

    public static void insertSort() {
        int arr[] = {12,234,1,123,45,12,234,1,123,45,23,2,0,4,3,2,6788823,2,0,4,3,2,678882,234,1,123,45,12,234,1,123,45,23,2,0,4,3,2,6788823,2,0,4,3,2,67888};
        for (int i=1; i<arr.length; i++) {
            for(int j=i; j>0&&arr[j] > arr[j-1];j--) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        for (int i:arr
             ) {
            System.out.println(i);
        }
    }

    public static void selectSort() {
        int arr[] = {12,234,1,123,45,12,234,1,123,45,23,2,0,4,3,2,6788823,2,0,4,3,2,67888};
        for (int i = 0; i <arr.length ; i++) {
            int min = i;
            for(int j=i+1; j<arr.length; j++) {
                if(arr[min] > arr[j]) {
                    min = j;
                }
            }
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }

        for (int i: arr
             ) {
            System.out.println(i);
        }
    }

    /**
     * 希尔排序（数据分组后，然后进行插入排序）
     */
    public static void shellSort() {
        int arr[] = {12,2,0,4,3,2,6788823,2,0,4,3,2,67888};
        int h = 1;
        int n = arr.length;
        while (h <= n/3) {
            h = h*3 + 1;
        }

        while (h >= 1) {
            for(int i=h; i<n; i += h) {
                int j;
                for(j=i; j>=h && arr[j] > arr[j-h]; j-=h) {
                    int temp = arr[j];
                    arr[j] = arr[j-h];
                    arr[j-h] = temp;
                }
            }
            for (int i: arr
                    ) {
                System.out.print(i+",");
            }
            System.out.println();
            h = h/3;
        }
    }

    public static void merge(int a[], int lo, int mid, int hi) {

        int i = lo;
        int j = mid + 1;
        for(int k=lo; k<=hi; k++) {
            aux[k] = a[k];
        }

        for(int k=lo; k<hi; k++) {
            if(i>mid) {a[k] = aux[j++];}
            if(j<hi) {a[k] = aux[i++];}
            if(aux[i] < aux[j]) {a[k] = aux[j++];}
            else {a[k] = aux[i++];}
        }
    }

    public static void sort(int [] arr, int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        int mid = lo + (hi-lo)/2;
        sort(arr, lo, mid);
        sort(arr, mid+1, hi);
        merge(arr, lo, mid, hi);
    }

    public static void hash() {
        int arr[] = {1, 23, 21, 23, 4, 2342, 1, 1};
        int n = arr.length;
        int h = 1;
        while (h<=n/3) {
            h = 3*h + 1;
        }

        while (h > 0) {
            for(int i=0; i<n; i+=h) {
                int j;
                for(j=i; j>=h && arr[j] > arr[j-h]; j-=h) {
                    int temp = arr[j];
                    arr[j] = arr[j-h];
                    arr[j-h] = temp;
                }
            }
            h = h/3;
        }
        for(int a : arr) {
            System.out.println(a);
        }
    }



}
